'''
kNN: k Nearest Neighbors

Input:      inX: 用于分类的数据 (1xN，测试集)
            dataSet: 用于训练的数据 (MxN，训练集)
            labels: 已知数据集的分类标签 (1xM)
            k: 选择距离最小的k个点
            
Output:     结果-分类标签
'''
from numpy import *
import operator

def classify0(inX, dataSet, labels, k):
    #dataSet的行数
    dataSetSize = dataSet.shape[0]
    #tile在列向量方向复制dataSetSize，重复dataSetSize次
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    #二维相减后分别平方
    sqDiffMat = diffMat**2
    #sum(1)为行相加
    sqDistances = sqDiffMat.sum(axis=1)
    #开方得到欧式距离
    distances = sqDistances**0.5
    #返回distances中元素从小到大排序后的索引值
    sortedDistIndicies = distances.argsort()     
    classCount={}
    #排序后取k个距离最近的数据
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    #降序排列字典
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    #返回最可能的数据集分类
    return sortedClassCount[0][0]


'''
file2matrix: 文件转矩阵

Input:      filename: 文件路径

Output:     returnMat： 数据集
            classLabelVector： 标签向量
'''

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector


"""
函数说明:对数据进行归一化

Parameters:
    dataSet - 特征矩阵
Returns:
    normDataSet - 归一化后的特征矩阵
    ranges - 数据范围
    minVals - 数据最小值
"""

def autoNorm(dataSet):
    #获取某个特征纬度的最大和最小值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    #根据最大值和最小值确定范围
    ranges = maxVals - minVals
    #返回dataSet的矩阵行列数
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    #根据公式，newValue = (oldValue - min) / (max - min)。先原始值减去最小值
    normDataSet = dataSet - tile(minVals, (m,1))
    #再除以最大和最小值的差,得到归一化数据
    normDataSet = normDataSet/tile(ranges, (m,1))
    #返回归一化数据结果,数据范围,最小值
    return normDataSet, ranges, minVals